1. Field of the Invention
The invention is directed to a method and apparatus for generating multiples of a BCD (Binary Coded Decimal) number in a high speed digital computer.
1a. Cross Reference to Related Patents
The following U.S. patent(s) is/are assigned to the assignee of the present application, is/are related to the present application and its/their disclosures is/are incorporated herein by reference:
(A) U.S. Pat. No. 4,817,048 issued Mar. 28, 1989 to Rawlinson et al and entitled, DIVIDER WITH QUOTIENT DIGIT PREDICTION.
2. Description of the Related Art
Computations may be carried out within a computer under a variety of number coding systems, including a simple binary coded (SBC) system and a binary coded decimal (BCD) system.
In a simple binary coded (SBC) numbering system, the numbers zero through fifteen are represented by the 4-bit code series, 0000, 0001, 0010, . . . , 1110, 1111.
In the binary coded decimal (BCD) numbering system, the decimal digits, zero through nine, are similarly represented by the 4-bit code series, 0000, 0001, 0010, 1000, 1001. But the remaining 4-bit codes, 1010 through 1111, have no numerical meaning. Numbers in the range ten through fifteen are represented by two 4-bit codes (two digits), as are all further numbers up to ninety-nine.
The simple binary coded (SBC) numbering system is generally preferred for carrying out arithmetic computations. This is so because there is an almost natural transformation as one moves from the functions of basic digital circuit components to basic arithmetic operations in the SBC system. The logic exclusive-OR gate, for example, inherently performs a two bit addition in the SBC system. The logic AND gate inherently performs a two-bit multiplication in the SBC system. And the binary SHIFT means inherently performs divide-by-two and multiply-by-two operations on SBC numbers of all bit lengths.
Such is not the case for numbers represented within the binary coded decimal (BCD) numbering system. A one-bit shift-left operation on, for example, a binary coded decimal six (represented by the bit series: 0000 0110) does not produce a binary coded decimal twelve (represented by the bit series: 0001 0010). Instead, it produces a bit series (0000 1100) which has no meaning in the domain of binary coded decimal numbers.
Similarly, a one-bit shift-right operation on a binary coded decimal twelve (represented by the bit series 0001 0010) does not produce a BCD six but rather a bit series (0000 1001) which represents the digits "09" in the BCD numbering system.
A different and more complex set of bit-manipulation rules have to be followed within a digital computer for performing arithmetic operations such as addition, subtraction, multiplication and division in the binary coded decimal (BCD) system as opposed to doing the same in the SBC system.
Despite these difficulties, there are instances where it is advantageous to carry out arithmetic computations directly on BCD numbers, without transforming the BCD numbers into simple binary coded numbers. By way of example, a financial institution may have voluminous amounts of data stored in BCD format. The processing of such data may take too long if back and forth transformations from the BCD system to the simple binary coded system have to be performed for each record.
When multiplication and division operations are to be carried out directly on BCD formatted numbers, it is advantageous to be able to quickly generate signals representing the one-times (.times.1) through nine-times (.times.9) multiples of every multi-digit BCD (Binary Coded Decimal) number that can be represented by a predefined number of bits (e.g. 64 bits).
If a first BCD number (multiplicand) is to be multiplied by a second BCD number (multiplier), the final product is typically generated by adding shifted multiples of the multiplicand. These multiples are commonly referred to as "partial products." Each partial product is equal to the product of the multiplicand and a corresponding single digit within the multiplier.
In decimal division, each digit of the quotient is typically formed by testing for a negative result while subtracting consecutive multiples of the divisor from a partial remainder. The final quotient digit is the one corresponding to the last tried multiple before the subtraction result becomes negative.
Previous approaches to generating multiples of a BCD multiplicand or of a BCD divisor consume either excessive amounts of computer time or excessive amounts of circuit space.
Generating the .times.0 and .times.1 multiples of a BCD number is trivial, but the remaining .times.2 (time two) through .times.9 (times nine) multiples present a problem.
Consider what happens, if a brute force method is used for generating all the .times.2 to .times.9 multiples of a multi-digit BCD number.
The contemplated brute force method uses a BCD adder having two inputs and an output. A BCD adder, incidentally, is a device which outputs a binary-coded decimal signal representing a sum when respective first and second BCD input signals are applied to its inputs. When speed is important, the BCD adder is typically implemented by using purely combinatorial logic circuits (e.g., AND and OR gates) as opposed to synchronous logic circuits (e.g., flip flops).
In the brute force method, a first register (operand register) is coupled to one input of the BCD adder while a second register (accumulator) is coupled to the other input. A synchronous feedback circuit is provided for writing, into the accumulator, a result output by the BCD adder in a previous machine cycle.
In a first machine cycle, the BCD number is written into the first and second registers (operand and accumulator registers). The number in the second register (accumulator) represents the times-one multiple of the original BCD number.
During a following, second machine cycle, the values in first and second registers are summed by the BCD adder and the result is written back into the second register (accumulator). Now, the number in the accumulator represents the times-two multiple of the original BCD number.
A times-three multiple forms in the accumulator at the end of the third machine cycle. A times-four multiple forms at the end of the fourth cycle, and so on.
Generally speaking, an accumulated sum representing the n-th multiple of the original BCD number forms in the accumulator after machine cycles (n=1,2, . . . ,9) A loop counter is typically included in the mechanism to help automate the procedure. The loop counter is initially loaded with the value, n, and it is decremented for each machine cycle until a zero count is reached. The zero count indicates the point in time when a desired multiple has been formed in the accumulator.
The obvious problem with this brute force approach is that it can take as many as 9 machine cycles just to generate a signal representing one multiple of a multi-digit BCD number. This is considered excessive.
A less obvious problem of the brute force method is that the resources of the BCD adder and three registers are disadvantageously tied up for as many as 9 cycles per multiple. The first tied-up register is the operand register which stores the original BCD number. The second tied-up register is the accumulator which is necessary for storing the result. And the third tied-up register is the loop counter which is required for maintaining the multiple count, n. These resources are unavailable for implementing other machine processes while they are tied up.
A more sophisticated approach shortens computation time by realizing that a .times.4 multiple can be generated in just two cycles if the .times.2 multiple generated in the first cycle is applied to both the first and second inputs of the BCD adder in the second cycle. The .times.8 multiple can be produced in a third cycle by again applying the accumulated result (the .times.4 multiple) simultaneously to the first and second inputs of the adder.
Alternatively, a .times.5 multiple can be produced in the third cycle after a .times.4 multiple has been formed in the second cycle, by re-applying the original BCD number to the first input of the BCD adder while the accumulated result (the .times.4 multiple) is applied to the second input. The .times.7 multiple can be produced by forming the .times.5 multiple in the accumulator and then adding the original BCD number two more times as indicated by: .times.5+.times.1+.times.2 (5 cycles).
The difficulty with the second approach is that, when a multiplier of fairly large size (e.g., 16 digits) appears in a decimal multiplication operation, it still takes a considerable number of machine cycles (e.g. as many as five cycles) per multiplier digit to form the desired multiples (e.g., the .times.5 and the .times.7 multiples) of the multiplicand. The total time for carrying out multiplications and divisions is still considered excessively long.
A third approach, which has been used recently in high performance machines such as the Amdahl 5990 mainframe, prestores the .times.3 and .times.4 multiples in side registers before a multiplication routine begins and then draws on these prestored values to more quickly generate the .times.5, .times.6, .times.7 and .times.8 multiples (.times.5=.times.4+.times.1; .times.6=.times.3+.times.3; .times.7=.times.3+.times.4; .times.8=.times.4+'4; .times.9=.times.3+.times.3+.times.3).
A major drawback of the third approach is that it consumes more registers and still requires as many as three cycles per multiplier digit.